{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Zigzag Iterator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #design #queue #array #iterator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #设计 #队列 #数组 #迭代器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ZigzagIterator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #锯齿迭代器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出两个一维的向量，请你实现一个迭代器，交替返回它们中间的元素。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "v1 = [1,2]\n",
    "v2 = [3,4,5,6] \n",
    "\n",
    "<strong>输出:</strong> <code>[1,3,2,4,5,6]\n",
    "\n",
    "<strong>解析:</strong></code>&nbsp;通过连续调用 <em>next</em> 函数直到 <em>hasNext</em> 函数返回 <code>false，</code>\n",
    "&nbsp;    <em>next</em> 函数返回值的次序应依次为: <code>[1,3,2,4,5,6]。</code></pre>\n",
    "\n",
    "<p><strong>拓展：</strong>假如给你&nbsp;<code>k</code>&nbsp;个一维向量呢？你的代码在这种情况下的扩展性又会如何呢?</p>\n",
    "\n",
    "<p><strong>拓展声明：</strong><br>\n",
    "&nbsp;&ldquo;锯齿&rdquo; 顺序对于&nbsp;<code>k &gt; 2</code>&nbsp;的情况定义可能会有些歧义。所以，假如你觉得 &ldquo;锯齿&rdquo; 这个表述不妥，也可以认为这是一种&nbsp;&ldquo;循环&rdquo;。例如：</p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "[1,2,3]\n",
    "[4,5,6,7]\n",
    "[8,9]\n",
    "\n",
    "<strong>输出: </strong><code>[1,4,8,2,5,9,3,6,7]</code>.\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zigzag-iterator](https://leetcode.cn/problems/zigzag-iterator/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zigzag-iterator](https://leetcode.cn/problems/zigzag-iterator/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]\\n[3,4,5,6]', '[1]\\n[]', '[]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1=v1\n",
    "        self.v2=v2\n",
    "        self.bound=2*min(len(self.v1),len(self.v2))\n",
    "        self.longer=self.v1 if len(self.v1)>len(self.v2) else self.v2\n",
    "        self.point=0\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if self.point%2==0:\n",
    "            if self.point<self.bound:\n",
    "                ret=self.v1[self.point//2]\n",
    "            else:\n",
    "                ret=self.longer[self.point-self.bound//2]\n",
    "        else:\n",
    "            if self.point<self.bound:\n",
    "                ret=self.v2[(self.point-1)//2]\n",
    "            else:\n",
    "                ret=self.longer[self.point-self.bound//2]\n",
    "        self.point+=1\n",
    "        return ret\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if len(self.v1)+len(self.v2)>self.point:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        p = 0\n",
    "        self.arr = []\n",
    "        while p < len(v1) and p < len(v2):\n",
    "            self.arr.append(v1[p])\n",
    "            self.arr.append(v2[p])\n",
    "            p += 1\n",
    "        self.arr += v1[p:]\n",
    "        self.arr += v2[p:]\n",
    "        self.p = 0\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.p += 1\n",
    "        return self.arr[self.p - 1]\n",
    "        \n",
    "    def hasNext(self) -> bool:\n",
    "        return self.p < len(self.arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.i = 0\n",
    "        self.dat = []\n",
    "        j = 0\n",
    "        while j < min(len(v1), len(v2)):\n",
    "            self.dat.append(v1[j])\n",
    "            self.dat.append(v2[j])\n",
    "            j += 1\n",
    "        if j < len(v1):\n",
    "            self.dat.extend(v1[j:])\n",
    "        if j < len(v2):\n",
    "            self.dat.extend(v2[j:])\n",
    "        self.total = len(self.dat)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        temp = self.dat[self.i]\n",
    "        self.i += 1\n",
    "        return temp\n",
    "        \n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.i < self.total\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1 = v1\n",
    "        self.v2 = v2\n",
    "        self.len1 = len(v1)\n",
    "        self.len2 = len(v2)\n",
    "        self.idx1 = 0\n",
    "        self.idx2 = 0\n",
    "        self.turn = 1\n",
    "        \n",
    "\n",
    "    def next(self) -> int:\n",
    "        if self.turn ==1 and self.idx1 < self.len1:\n",
    "            s = self.v1[self.idx1]\n",
    "            self.idx1+=1\n",
    "            self.turn = 2\n",
    "        elif self.turn ==2 and self.idx2 < self.len2:\n",
    "            s = self.v2[self.idx2]\n",
    "            self.idx2+=1\n",
    "            self.turn = 1\n",
    "        elif self.idx1<self.len1:\n",
    "            s = self.v1[self.idx1]\n",
    "            self.idx1+=1\n",
    "        elif self.idx2<self.len2:\n",
    "            s = self.v2[self.idx2]\n",
    "            self.idx2+=1\n",
    "        return s\n",
    "        \n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.idx1 < self.len1 or self.idx2<self.len2\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.flag = 0\n",
    "        self.pt = 0\n",
    "        self.locked = False\n",
    "        self.v1 = v1\n",
    "        self.v2 = v2\n",
    "        if self.v1 == []:\n",
    "            self.locked = True\n",
    "            self.flag = 1\n",
    "        if self.v2 == []:\n",
    "            self.locked = True\n",
    "\n",
    "    def next(self) -> int:\n",
    "        locked = False\n",
    "        res = 0\n",
    "        if self.flag == 0:\n",
    "            res = self.v1[self.pt]\n",
    "            if self.pt == len(self.v1) - 1:\n",
    "                locked = True\n",
    "            if self.locked:\n",
    "                self.pt += 1\n",
    "        else:\n",
    "            res = self.v2[self.pt]\n",
    "            if self.pt == len(self.v2) - 1:\n",
    "                locked = True\n",
    "            self.pt += 1\n",
    "        if not self.locked:\n",
    "            self.flag = 1 - self.flag\n",
    "            self.locked = locked\n",
    "        print(res)\n",
    "        return res\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if self.locked:\n",
    "            if self.flag == 0 and self.pt >= len(self.v1) or self.flag == 1 and self.pt >= len(self.v2):\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        p = 0\n",
    "        self.arr = []\n",
    "        while p < len(v1) and p < len(v2):\n",
    "            self.arr.append(v1[p])\n",
    "            self.arr.append(v2[p])\n",
    "            p += 1\n",
    "        self.arr += v1[p:]\n",
    "        self.arr += v2[p:]\n",
    "        self.p = 0\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.p += 1\n",
    "        return self.arr[self.p - 1]\n",
    "        \n",
    "    def hasNext(self) -> bool:\n",
    "        return self.p < len(self.arr)\n",
    "\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        p = 0\n",
    "        self.arr = []\n",
    "        while p < len(v1) and p < len(v2):\n",
    "            self.arr.append(v1[p])\n",
    "            self.arr.append(v2[p])\n",
    "            p += 1\n",
    "        self.arr += v1[p:]\n",
    "        self.arr += v2[p:]\n",
    "        self.p = 0\n",
    "        \n",
    "    def next(self) -> int:\n",
    "        self.p += 1\n",
    "        return self.arr[self.p-1]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.p < len(self.arr)\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "使用queue存储两个迭代器，这样就可以zigzag的打印出里面的值\n",
    "时间复杂度每个方法都是: O(1)\n",
    "空间复杂度: O(N)\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "      self.queue = deque()\n",
    "      if v1:\n",
    "        self.queue.append((iter(v1), len(v1)))\n",
    "      if v2:\n",
    "        self.queue.append((iter(v2), len(v2)))\n",
    "\n",
    "    def next(self) -> int:\n",
    "      if self.hasNext(): \n",
    "        next_iter, length = self.queue.popleft()\n",
    "        res = next(next_iter)\n",
    "        length -= 1\n",
    "        if length > 0:\n",
    "          self.queue.append((next_iter, length))\n",
    "        return res\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "      return len(self.queue) != 0\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1=v1\n",
    "        self.v2=v2\n",
    "        self.bound=2*min(len(self.v1),len(self.v2))\n",
    "        self.longer=self.v1 if len(self.v1)>len(self.v2) else self.v2\n",
    "        self.point=0\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if self.point%2==0:\n",
    "            if self.point<self.bound:\n",
    "                ret=self.v1[self.point//2]\n",
    "            else:\n",
    "                ret=self.longer[self.point-self.bound//2]\n",
    "        else:\n",
    "            if self.point<self.bound:\n",
    "                ret=self.v2[(self.point-1)//2]\n",
    "            else:\n",
    "                ret=self.longer[self.point-self.bound//2]\n",
    "        self.point+=1\n",
    "        return ret\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if len(self.v1)+len(self.v2)>self.point:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.arr = []\n",
    "        self.idx = 0\n",
    "        n1 = len(v1)\n",
    "        n2 = len(v2)\n",
    "        p = 0\n",
    "        while p < n1 and p < n2:\n",
    "            self.arr.append(v1[p])\n",
    "            self.arr.append(v2[p])\n",
    "            p += 1\n",
    "        self.arr += v1[p:]\n",
    "        self.arr += v2[p:]\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.idx += 1\n",
    "        return self.arr[self.idx - 1]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.idx < len(self.arr)\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1=v1\n",
    "        self.v2=v2\n",
    "        self.i,self.j=0,0\n",
    "        self.n1=len(v1)\n",
    "        self.n2=len(v2)\n",
    "        self.flag=False\n",
    "    def next(self) -> int:\n",
    "        if self.hasNext():\n",
    "            if not self.flag:\n",
    "                if self.i<self.n1:\n",
    "                    self.i+=1\n",
    "                    self.flag=True\n",
    "                    return self.v1[self.i-1]\n",
    "                else:\n",
    "                    self.j+=1\n",
    "                    self.flag=True\n",
    "                    return self.v2[self.j-1]\n",
    "            else:\n",
    "                if self.j<self.n2:\n",
    "                    self.j+=1\n",
    "                    self.flag=False\n",
    "                    return self.v2[self.j-1]\n",
    "                else:\n",
    "                    self.i+=1\n",
    "                    self.flag=False\n",
    "                    return self.v1[self.i-1]\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.i<self.n1 or self.j<self.n2\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1, v2):\n",
    "        self.v1 = v1\n",
    "        self.v1_head = 0\n",
    "        self.v1_tail = len(self.v1)\n",
    "        \n",
    "        self.v2 = v2\n",
    "        self.v2_head = 0\n",
    "        self.v2_tail = len(self.v2)\n",
    "        \n",
    "        self.flag = True\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if not self.hasNext():\n",
    "            return False\n",
    "        \n",
    "        # 某一个队列没有元素了\n",
    "        if self.v1_head == self.v1_tail:\n",
    "            temp = self.v2[self.v2_head]\n",
    "            self.v2_head += 1\n",
    "            return temp\n",
    "        elif self.v2_head == self.v2_tail:\n",
    "            temp = self.v1[self.v1_head]\n",
    "            self.v1_head += 1\n",
    "            return temp\n",
    "        \n",
    "        if self.flag:\n",
    "            temp = self.v1[self.v1_head]\n",
    "            self.v1_head += 1\n",
    "            self.flag = not self.flag\n",
    "        else:\n",
    "            temp = self.v2[self.v2_head]\n",
    "            self.v2_head += 1\n",
    "            self.flag = not self.flag\n",
    "        return temp\n",
    "        \n",
    "    def hasNext(self) -> bool:\n",
    "        if self.v1_head == self.v1_tail and self.v2_head == self.v2_tail:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.l = [v1, v2]\n",
    "        self.ind = 0 \n",
    "        \n",
    "\n",
    "    def next(self) -> int:\n",
    "        v = self.l[self.ind].pop(0)\n",
    "        self.ind = (self.ind + 1) % 2\n",
    "        return v\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if len(self.l[self.ind]) > 0:\n",
    "            return True\n",
    "        \n",
    "        self.ind = (self.ind + 1) % 2\n",
    "        if len(self.l[self.ind]) > 0:\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.lst = []\n",
    "        order = 1\n",
    "        i = j = 0\n",
    "        m, n = len(v1), len(v2)\n",
    "        while i < m and j < n:\n",
    "            if order:\n",
    "                self.lst.append(v1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                self.lst.append(v2[j])\n",
    "                j += 1\n",
    "            order = 1 - order\n",
    "\n",
    "        self.lst += v1[i:] + v2[j:]\n",
    "        self.ind = 0\n",
    "        self.length = len(self.lst)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.ind += 1\n",
    "        return self.lst[self.ind - 1]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if self.ind >= self.length:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1=v1\n",
    "        self.v2=v2\n",
    "        self.i=0\n",
    "        self.j=0\n",
    "        self.lasti=len(v1)\n",
    "        self.lastj=len(v2)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if not self.hasNext():\n",
    "            return 0\n",
    "        if (self.i<=self.j and self.i<self.lasti) or (self.j==self.lastj):\n",
    "            self.i+=1\n",
    "            return self.v1[self.i-1]\n",
    "        else:\n",
    "            self.j+=1\n",
    "            return self.v2[self.j-1]\n",
    "    def hasNext(self) -> bool:\n",
    "        if self.i<self.lasti or self.j<self.lastj:\n",
    "            #print(self.i,self.lasti,self.j,self.lastj)\n",
    "            return True \n",
    "        return False\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "使用queue存储两个迭代器，这样就可以zigzag的打印出里面的值\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "      self.queue = deque()\n",
    "      if v1:\n",
    "        self.queue.append((iter(v1), len(v1)))\n",
    "      if v2:\n",
    "        self.queue.append((iter(v2), len(v2)))\n",
    "\n",
    "    def next(self) -> int:\n",
    "      if self.hasNext():\n",
    "        iter1, length = self.queue.popleft()\n",
    "        res = next(iter1)\n",
    "        length -= 1\n",
    "        # 只有当还有值存在的时候，才放入queue\n",
    "        if length > 0:\n",
    "          self.queue.append((iter1, length))\n",
    "        return res\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "      return len(self.queue)\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.arr = [v1, v2]\n",
    "        self.column = []\n",
    "        for item in self.arr:\n",
    "            self.column.append(-1)\n",
    "        self.row = -1\n",
    "\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.row = (self.row + 1) % len(self.arr)\n",
    "\n",
    "        cnt = 0\n",
    "        while self.column[self.row] == len(self.arr[self.row])-1:\n",
    "            self.row = (self.row + 1) % len(self.arr)\n",
    "            cnt += 1\n",
    "            if cnt == len(self.arr):\n",
    "                return None\n",
    "        \n",
    "        self.column[self.row] += 1\n",
    "\n",
    "        return self.arr[self.row][self.column[self.row]]\n",
    "\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        row = (self.row + 1) % len(self.arr)\n",
    "\n",
    "        cnt = 0\n",
    "        while self.column[row] == len(self.arr[row])-1:\n",
    "            row = (row + 1) % len(self.arr)\n",
    "            cnt += 1\n",
    "            if cnt == len(self.arr):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        p=0\n",
    "        mi=min(len(v1),len(v2))\n",
    "        self.arr=[]\n",
    "        while p<mi:\n",
    "            self.arr.append(v1[p])\n",
    "            self.arr.append(v2[p])\n",
    "            p+=1\n",
    "        self.arr+=v1[p:]\n",
    "        self.arr+=v2[p:]\n",
    "        self.p=0\n",
    "        self.n=len(self.arr)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.p+=1\n",
    "        return self.arr[self.p-1]\n",
    "        \n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.p<self.n\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.arr = [v1, v2]\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if not self.arr[0]:\n",
    "            self.arr = self.arr[::-1]\n",
    "        \n",
    "        res = self.arr[0].pop(0)\n",
    "        self.arr = self.arr[::-1]\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return not (self.arr[0] == self.arr[1] == [])\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.l = [v1, v2]\n",
    "        self.d = {\n",
    "            0: v1,\n",
    "            1: v2,\n",
    "        }\n",
    "        self.k = 1\n",
    "        self.avai = [0, 1]\n",
    "        self.idx = 0\n",
    "        self.pos = 0\n",
    "        self.process()\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if not self.hasNext():\n",
    "            return False\n",
    "        ans = self.l[self.idx][self.pos]\n",
    "        self.idx += 1\n",
    "        self.process()\n",
    "        return ans\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return len(self.l) > 0\n",
    "    \n",
    "    def process(self):\n",
    "        while self.l:\n",
    "            if self.idx < len(self.l):\n",
    "                if self.pos < len(self.l[self.idx]):\n",
    "                    return\n",
    "                else:\n",
    "                    self.l.pop(self.idx)\n",
    "                    continue\n",
    "            else:\n",
    "                self.idx = 0\n",
    "                self.pos += 1\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.arr = [v1, v2]\n",
    "\n",
    "    def next(self) -> int:\n",
    "        if not self.arr[0]:\n",
    "            self.arr = self.arr[::-1]\n",
    "        cur = self.arr[0].pop(0)\n",
    "        self.arr = self.arr[::-1]\n",
    "        return cur\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return not (self.arr[0] == [] and self.arr[1] == [])\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.i = 0\n",
    "        self.v = []\n",
    "        self.v.append(v1)\n",
    "        self.v.append(v2)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        res = 0\n",
    "        if len(self.v[self.i]) != 0:\n",
    "            res = self.v[self.i][0]\n",
    "            del self.v[self.i][0]\n",
    "        self.i += 1\n",
    "        if self.i == len(self.v):\n",
    "            self.i = 0\n",
    "        return res\n",
    "\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        while len(self.v) > 0 and len(self.v[self.i]) == 0:\n",
    "            del self.v[self.i]\n",
    "            if self.i == len(self.v):\n",
    "                self.i = 0\n",
    "        \n",
    "        if len(self.v) == 0 or len(self.v[self.i]) == 0:\n",
    "            return False\n",
    "        else: \n",
    "            return True\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import SimpleQueue\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v_list = [v1, v2]\n",
    "        self.queue = SimpleQueue()\n",
    "        for i in range(len(self.v_list)):\n",
    "            v = self.v_list[i]\n",
    "            if len(v) > 0:\n",
    "                self.queue.put(((i, 0 ,len(v))))\n",
    "        \n",
    "\n",
    "    def next(self) -> int:\n",
    "        cur = self.queue.get()\n",
    "        new = (cur[0], cur[1] + 1, cur[2])\n",
    "        if new[1] < new[2]:\n",
    "            self.queue.put(new)\n",
    "        return self.v_list[cur[0]][cur[1]]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.queue.qsize() > 0\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.m = len(v1)\n",
    "        self.n = len(v2)\n",
    "        if self.m > self.n:\n",
    "            v2 = v2 + [inf] * (self.m - self.n)\n",
    "        else:\n",
    "            v1 = v1 + [inf] * (self.n - self.m)\n",
    "        L = []\n",
    "        for a, b in zip(v1, v2):\n",
    "            if a != inf:\n",
    "                L.append(a)\n",
    "            if b != inf:\n",
    "                L.append(b)\n",
    "        self.ans = L \n",
    "        self.i = 0\n",
    "        self.lenOfL = len(L)\n",
    " \n",
    "    def next(self) -> int:\n",
    "        self.i += 1\n",
    "        return self.ans[self.i - 1]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.i <= self.lenOfL - 1\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1 = v1\n",
    "        self.v2 = v2\n",
    "        self.index = 0\n",
    "    def next(self) -> int:\n",
    "        if self.index == 0 and self.v1:\n",
    "                res = self.v1.pop(0)\n",
    "                self.index = 1\n",
    "        elif self.index == 1 and self.v2:\n",
    "                res = self.v2.pop(0)\n",
    "                self.index = 0\n",
    "        elif self.v2:\n",
    "                res = self.v2.pop(0)\n",
    "        elif self.v1:\n",
    "                res = self.v1.pop(0)                \n",
    "        return res\n",
    "        \n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.v1 or self.v2\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1 = collections.deque(v1)\n",
    "        self.v2 = collections.deque(v2)\n",
    "        self.turn = 0\n",
    "        \n",
    "\n",
    "    def next(self) -> int:\n",
    "        if self.turn == 0 and self.v1:\n",
    "            self.turn = 1\n",
    "            return self.v1.popleft()\n",
    "        elif self.turn == 1 and self.v2:\n",
    "            self.turn = 0\n",
    "            return self.v2.popleft()\n",
    "        elif self.v1:\n",
    "            return self.v1.popleft()\n",
    "        else:\n",
    "            return self.v2.popleft()\n",
    "        \n",
    "        \n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return len(self.v1) + len(self.v2) > 0\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.queue1=deque(v1)\n",
    "        self.queue2=deque(v2)\n",
    "        self.length=-1\n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.length+=1\n",
    "        if self.length%2==0 and len(self.queue1)>0:\n",
    "            return self.queue1.popleft()\n",
    "        elif self.length%2!=0 and len(self.queue2)>0:\n",
    "            return self.queue2.popleft()\n",
    "        return self.queue1.popleft() if len(self.queue1)>0 else self.queue2.popleft()\n",
    "    def hasNext(self) -> bool:\n",
    "        return len(self.queue1)>0 or len(self.queue2)>0\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.flag = 0\n",
    "        self.pt = 0\n",
    "        self.locked = False\n",
    "        self.v1 = v1\n",
    "        self.v2 = v2\n",
    "        if self.v1 == []:\n",
    "            self.locked = True\n",
    "            self.flag = 1\n",
    "        if self.v2 == []:\n",
    "            self.locked = True\n",
    "\n",
    "    def next(self) -> int:\n",
    "        locked = False\n",
    "        res = 0\n",
    "        if self.flag == 0:\n",
    "            res = self.v1[self.pt]\n",
    "            if self.pt == len(self.v1) - 1:\n",
    "                locked = True\n",
    "            if self.locked:\n",
    "                self.pt += 1\n",
    "        else:\n",
    "            res = self.v2[self.pt]\n",
    "            if self.pt == len(self.v2) - 1:\n",
    "                locked = True\n",
    "            self.pt += 1\n",
    "        if not self.locked:\n",
    "            self.flag = 1 - self.flag\n",
    "            self.locked = locked\n",
    "        # print(res)\n",
    "        return res\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if self.locked:\n",
    "            if self.flag == 0 and self.pt >= len(self.v1) or self.flag == 1 and self.pt >= len(self.v2):\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.i = 0\n",
    "        self.v = []\n",
    "        self.v.append(v1)\n",
    "        self.v.append(v2)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        res = 0\n",
    "        if len(self.v[self.i]) != 0:\n",
    "            res = self.v[self.i][0]\n",
    "            del self.v[self.i][0]\n",
    "        self.i += 1\n",
    "        if self.i == len(self.v):\n",
    "            self.i = 0\n",
    "        return res\n",
    "\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        while len(self.v) > 0 and len(self.v[self.i]) == 0:\n",
    "            del self.v[self.i]\n",
    "            if self.i == len(self.v):\n",
    "                self.i = 0\n",
    "        \n",
    "        if len(self.v) == 0:\n",
    "            return False\n",
    "        else: \n",
    "            return True\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "使用queue存储两个迭代器，这样就可以zigzag的打印出里面的值\n",
    "时间复杂度每个方法都是: O(1)\n",
    "空间复杂度: O(N)\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "      self.queue = deque()\n",
    "      if v1:\n",
    "        self.queue.append((iter(v1), len(v1)))\n",
    "      if v2:\n",
    "        self.queue.append((iter(v2), len(v2)))\n",
    "\n",
    "    def next(self) -> int:\n",
    "      if self.hasNext() and self.queue:\n",
    "        next_iter, length = self.queue.popleft()\n",
    "        res = next(next_iter)\n",
    "        length -= 1\n",
    "        if length > 0:\n",
    "          self.queue.append((next_iter, length))\n",
    "        return res\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "      return len(self.queue)\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v = collections.deque()\n",
    "        m, n = len(v1), len(v2)\n",
    "        l = min(m, n)\n",
    "        for i in range(l):\n",
    "            self.v.append(v1[i])\n",
    "            self.v.append(v2[i])\n",
    "        self.v.extend(v1[l:])\n",
    "        self.v.extend(v2[l:])\n",
    "        \n",
    "    def next(self) -> int:\n",
    "        return self.v.popleft()\n",
    "        \n",
    "    def hasNext(self) -> bool:\n",
    "        return len(self.v) > 0\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.arr = []\n",
    "        self.index = 0\n",
    "        i, j = 0, 0\n",
    "        while i<len(v1) or j<len(v2):\n",
    "            if i < len(v1):\n",
    "                self.arr.append(v1[i])\n",
    "                i += 1\n",
    "            if j < len(v2):\n",
    "                self.arr.append(v2[j])\n",
    "                j += 1\n",
    "        \n",
    "\n",
    "    def next(self) -> int:\n",
    "        tmp = self.arr[self.index]\n",
    "        self.index += 1\n",
    "        return tmp\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.index < len(self.arr)\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        if v1:\n",
    "            self.flag = 0\n",
    "        else:\n",
    "            self.flag = 1\n",
    "        self.v1 = v1\n",
    "        self.v2 = v2\n",
    "    def next(self) -> int:\n",
    "        if self.flag:\n",
    "            if self.v1:\n",
    "                self.flag = 0\n",
    "            return self.v2.pop(0)\n",
    "        else:\n",
    "            if self.v2:\n",
    "                self.flag = 1\n",
    "            return self.v1.pop(0)\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if self.flag:\n",
    "            if self.v2:\n",
    "                return True\n",
    "        else:\n",
    "            if self.v1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.v1=v1\n",
    "        self.v2=v2\n",
    "        self.i,self.j=0,0\n",
    "        self.n1=len(v1)\n",
    "        self.n2=len(v2)\n",
    "        self.flag=False\n",
    "    def next(self) -> int:\n",
    "        if self.hasNext():\n",
    "            if not self.flag:\n",
    "                if self.i<self.n1:\n",
    "                    self.i+=1\n",
    "                    self.flag=True\n",
    "                    return self.v1[self.i-1]\n",
    "                else:\n",
    "                    self.j+=1\n",
    "                    self.flag=True\n",
    "                    return self.v2[self.j-1]\n",
    "            else:\n",
    "                if self.j<self.n2:\n",
    "                    self.j+=1\n",
    "                    self.flag=False\n",
    "                    return self.v2[self.j-1]\n",
    "                else:\n",
    "                    self.i+=1\n",
    "                    self.flag=False\n",
    "                    return self.v1[self.i-1]\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.i<self.n1 or self.j<self.n2\n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZigzagIterator:\n",
    "    def __init__(self, v1: List[int], v2: List[int]):\n",
    "        self.lst = []\n",
    "        self.ind = 0\n",
    "        i, j = 0 , 0 \n",
    "        m, n = len(v1), len(v2)\n",
    "        order = 1\n",
    "        while i < m and j < n:\n",
    "            if order:\n",
    "                self.lst.append(v1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                self.lst.append(v2[j])\n",
    "                j += 1\n",
    "            order = 1 -order\n",
    "        self.lst += v1[i:] + v2[j:]\n",
    "        self.length = len(self.lst)\n",
    "        # print(self.lst)\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "    def next(self) -> int:\n",
    "        self.ind += 1\n",
    "        return self.lst[self.ind-1]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        if self.ind >= self.length:\n",
    "            return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "# Your ZigzagIterator object will be instantiated and called as such:\n",
    "# i, v = ZigzagIterator(v1, v2), []\n",
    "# while i.hasNext(): v.append(i.next())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
